﻿//https://leetcode.cn/problems/delete-and-earn/
//class Solution {
//public:
//    int deleteAndEarn(vector<int>& nums) {
//        const int N = 10001;
//        int arr[N] = { 0 };
//        for (auto x : nums)
//            arr[x] += x;
//        // 创建dp表;
//        vector<int> f(N);
//        vector<int> g(N);
//        f[0] = arr[0];
//        g[0] = 0;
//        for (int i = 1; i < N; i++) {
//
//            f[i] = g[i - 1] + arr[i];
//            g[i] = max(g[i - 1], f[i - 1]);
//        }
//        return max(f[N - 1], g[N - 1]);
//    }
//};
//
//
//
//
//
//
//https://leetcode.cn/problems/JEj789/submissions/586565023/
//class Solution {
//public:
//    int minCost(vector<vector<int>>& costs) {
//        int num = costs.size();
//        vector<vector<int>> dp(num + 1, vector<int>(3));
//        for (int i = 1; i <= num; i++) {
//            dp[i][0] = min(dp[i - 1][1], dp[i - 1][2]) + costs[i - 1][0];
//            dp[i][1] = min(dp[i - 1][0], dp[i - 1][2]) + costs[i - 1][1];
//            dp[i][2] = min(dp[i - 1][0], dp[i - 1][1]) + costs[i - 1][2];
//        }
//        return min(min(dp[num][0], dp[num][1]), dp[num][2]);
//    }
//};
//
//
//
//https://leetcode.cn/problems/dungeon-game/description/
//class Solution {
//public:
//    int calculateMinimumHP(vector<vector<int>>& dungeon) {
//        // 创建dp表;
//        int row = dungeon.size();
//        int col = dungeon[0].size();
//        // 初始化
//        vector<vector<int>> dp(row + 1, vector<int>(col + 1, INT_MAX));
//        dp[row][col - 1] = dp[row - 1][col] = 1;
//        for (int i = row - 1; i >= 0; i--) {
//            for (int j = col - 1; j >= 0; j--) {
//                // 1.dp[i][j]表示从起点开始,到达[i,j]位置时，所需的最低初始健康点数;(❌);
//                // 2.dp[i][j]表示从[i,j]位置出发,到达终点,所需的最低初始健康点数;(✔);
//                dp[i][j] = min(dp[i + 1][j], dp[i][j + 1]) - dungeon[i][j];
//                dp[i][j] = max(1, dp[i][j]);
//            }
//        }
//        return dp[0][0];
//    }
//};
//
//
//https://leetcode.cn/problems/the-masseuse-lcci/description/
//class Solution {
//public:
//    int massage(vector<int>& nums) {
//        int n = nums.size();
//        if (n == 0)
//            return 0;
//        vector<int> f(n);
//        vector<int> g(n);
//        f[0] = nums[0];
//        g[0] = 0;
//        for (int i = 1; i < n; i++) {
//            f[i] = g[i - 1] + nums[i];
//            g[i] = max(f[i - 1], g[i - 1]);
//        }
//        return max(f[n - 1], g[n - 1]);
//    }
//};
//
//
//
//https://leetcode.cn/problems/PzWKhm/description/
//class Solution {
//public:
//    int rob(vector<int>& nums) {
//        int n = nums.size();
//        return max(nums[0] + rob1(nums, 2, n - 2), rob1(nums, 1, n - 1));
//    }
//    int rob1(vector<int>& nums, int left, int right) {
//        int n = nums.size();
//        vector<int> f(n);
//        vector<int> g(n);
//        if (left > right)
//            return 0;
//        // 初始化;
//        f[left] = nums[left];
//        for (int i = left + 1; i <= right; i++) {
//            f[i] = g[i - 1] + nums[i];
//            g[i] = max(g[i - 1], f[i - 1]);
//        }
//        return max(f[right], g[right]);
//    }
//};
//
//
//
//
//https://leetcode.cn/problems/Gu0c2T/description/
//class Solution {
//public:
//    int rob(vector<int>& nums) {
//        int length = nums.size();
//        vector<int> dp(length, 0);
//        dp[0] = nums[0];
//        if (length == 0)
//        {
//            return 0;
//        }
//        if (length == 1)
//        {
//            return nums[0];
//        }
//        dp[1] = max(nums[0], nums[1]);
//        for (int i = 2; i < length; i++)
//        {
//            dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]);
//        }
//        return dp[length - 1];
//    }
//};